This invention relates generally to memory systems for storage and retrieval of digital data, and, more particularly, relates to apparatus and methods for providing high-speed, multi-port Random Access Memory (RAM) and Read-Only Memory (ROM).
Multi-port RAM and ROM devices are widely utilized in digital computers and communications systems. These multi-port devices are intended to reduce data access time by providing several simultaneous paths to the data. In conventional multi-port RAM, for example, the data path includes a decoder that translates an externally supplied memory address into a set of internal signals. These internal signals activate selected internal memory cells corresponding to the external address. The external address may be, for example, an n-bit binary number that is decoded into one of 2.sup.n internal addresses. Multi-port RAM devices also utilize a data path in which a selected plurality of activated memory cells are connected to the data ports in response to the externally supplied address. The data paths enable several RAM ports to read and write data.
In the simplest multi-port configuration, the entire decoder/selector path is duplicated for each port. The ports can be used to READ or WRITE data without interacting, unless they address the same memory cells. Path-independence permits external devices connected to the various ports to share data conveniently, with low latency and high bandwidth.
Multi-port memory devices of this type, however, have significant limitations. In particular, the necessary duplication of nearly the entire memory system--except for the shared multi-port memory cells--multiplies the cost and complexity of the device. In addition to duplication of the memory system, the multi-port memory cell itself must have more wires and ports than its single-port counterpart. Multi-port RAM of this configuration thus occupies significantly more area than does single-port RAM, further increasing the cost and size of integrated circuit implementations.
Additionally, because a multi-port RAM of conventional design is larger, its internal wires must be longer. These wires therefore have higher capacitance, which reduces speed. Multi-port RAMs, as a result, tend to be slower than single-port RAMs of the same number of bits.
In an attempt to avoid the area-related costs entailed by multiple-pathway multi-port RAM, a second class of multi-port AM utilizes memory cells having fewer ports and reduced wiring area. However, in these devices, the narrow data path cannot support completely independent access from the ports to the memory cells. Occasionally, several ports will try to simultaneously use a part of the data path that is too narrow to support all of the requests. When two ports address neighboring data words, for example, each port's request cannot be simultaneously serviced, and a "conflict" arises. Such conflicts can be resolved by controlling the ports to access neighboring data words at different times--i.e., time-domain multiplexing. This multiplexing, however, imposes a time and speed penalty.
Conventional time-domain multiplexing techniques can be divided into two classes: deterministic and stochastic. In deterministic systems, the speed penalty associated with time-domain multiplexing is incurred on every data access operation. Stochastic approaches involve a degree of randomness that permits the time penalty to be avoided on some, but not all, data accesses.
In multi-port RAM devices utilizing deterministic time-domain multiplexing, the memory system can utilize a RAM cell having fewer ports than the overall memory system. A dual-port RAM system, for example, can utilize single-port memory cells.
Although the deterministic configuration requires less wire and area, the path to the data is narrower, and has reduced bandwidth, compared to a single-port RAM. Thus, the deterministic memory system is slower overall than is a single-port RAM. For example, a known technique for constructing a dual-port RAM from single-port cells involves time-sharing the access path so that the ports alternate accesses. First one port gains exclusive access to the decoder and memory cells; then, the second port is permitted to use these resources; then the access cycle repeats. The overall speed of the dual-port RAM is therefore approximately half that of the single-port RAM.
In conventional multi-port RAM system utilizing stochastic time-domain multiplexing, wiring and area requirements are reduced by providing a narrower path to the memory cells. This narrow path is usually insufficient to support the most general form of multi-port access, so the memory system is divided into subsystems--referred to as "bins"--and part of the decoder path is duplicated. In a dual-port RAM having stochastic time-domain multiplexing, when Port A is requested to access data in one bin and Port B is requested to access data in a different bin, both ports can service these requests simultaneously, because separate paths exist between the bins and the ports.
However, if both ports attempt to access a memory location in the same bin, a conflict arises. Because only a portion of the data path between ports and memory cells is duplicated--i.e., the section from the ports to the bins--the ports occasionally attempt to use the same resources for different purposes. Both ports cannot obtain correct data if a conflict arises. Thus, conventional practice requires that at least one port wait when a conflict occurs. This additional delay, experienced by at least one of the ports during a conflict, further reduces average system speed, and the non-deterministic nature of the delay increases the complexity of the system containing the multi-port RAM.
It is accordingly an object of the invention to provide improved multi-port memory devices having enhanced operational speed.
Another object of the invention is to provide multi-port memory apparatus requiring less cell and wiring area than that of conventional multi-port memory devices.
A further object of the invention is to provide a memory system in which accessing conflicts do not require memory ports to access data words at different times.
It is another object of the present invention to provide multi-port memory apparatus that avoids the delay inherent in multi-port memory devices utilizing deterministic time-domain multiplexing.
A further object of the invention is to provide a multi-port memory system that eliminates non-deterministic delay, thereby accelerating memory operations and simplifying implementation of the multi-port memory device.
Other general and specific objects of the invention will in part be obvious and will in part appear hereinafter.